import collections


class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        s = preorder.split(',')
        n = len(s)
        index = 1
        stack = collections.deque([0])
        if s[0] == '#':
            if len(s) == 1:
                return True
            else:
                return False
        state = 0
        while stack and index < n:
            if state == 0:
                if s[index] != '#':
                    stack.append(0)
                else:
                    state = 1
            else:
                if s[index] == '#':
                    stack.pop()
                else:
                    stack.pop()
                    stack.append(0)
                    state = 0
            index += 1
        if stack or (not stack and index < n):
            return False
        else:
            return True


data = Solution()
preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
print(data.isValidSerialization(preorder))
preorder = "1,#"
print(data.isValidSerialization(preorder))
preorder = "9,#,#,1"
print(data.isValidSerialization(preorder))
